It is called labels matching problem when two labels of an instance come from two labelsets respectively in multi-label classification, however there is no any specific algorithm for solving such problem. Although the labels matching problem could be solved by tranditional multi-label classification algorithms, but this problem has its own particularity. After analyzing the labels matching problem, a new labels matching algorithm based on pairwise labelsets was proposed using adaptive method, which considered the real Adaptive Boosting (real AdaBoost) and the global optimization idea. This algorithm could learn the rule of labels matching well and complete matching. The experimental results show that, compared with the traditional algorithms, the new algorithm can not only reduce searching scope of the labels space, but also decrease the minimum learning error as the number of weak classifiers increases, and make the classification more accurate and faster.